|
In mathematics, the Sturm's sequence of a univariate polynomial is a sequence of polynomials associated with and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of located in an interval in terms of the number of changes of signs of the values of the Sturm's sequence at the bounds of the interval. Applied to the interval of all the real numbers, it gives the total number of real roots of . Whereas the fundamental theorem of algebra readily yields the overall number of complex roots, counted with multiplicity, it does not provide a procedure for calculating them. Sturm's theorem counts the number of distinct real roots and locates them in intervals. By subdividing the intervals containing some roots, it can isolate the roots into arbitrary small intervals, each containing exactly one root. This yields an arbitrary-precision numeric root finding algorithm for univariate polynomials. Sturm's sequence and Sturm's theorems are named after Jacques Charles François Sturm. ==Sturm chains== A Sturm chain or Sturm sequence is a finite sequence of polynomials : of decreasing degree with these following properties: * is square free (no square factors, i.e., no repeated roots); * if , then ; * if for then ; * does not change its sign. Sturm's sequence is a modification of Fourier's sequence. To obtain a Sturm chain, Sturm himself proposed to choose the intermediary results when applying Euclid's algorithm to and its derivative: : where and are the remainder and the quotient of the polynomial long division of by , and where is the minimal number of polynomial divisions (never greater than ) needed to obtain a zero remainder. That is, successively take the remainders with polynomial division and change their signs. Since for , the algorithm terminates. The final polynomial, , is the greatest common divisor of and its derivative. If is square free, it shares no roots with its derivative, hence will be a non-zero constant polynomial. The Sturm chain, called the canonical Sturm chain, then is : If is not square-free, this sequence does not formally satisfy the definition of a Sturm chain above; nevertheless it still satisfies the conclusion of Sturm's theorem (below). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sturm's theorem」の詳細全文を読む スポンサード リンク
|